Three-dimensional (3D) meshes are widely used in various applications for representing 3D objects, such as video games, engineering design, e-commerce, virtual reality, and architectural and scientific visualization. Usually their raw representation requires a huge amount of data. However, most applications prefer compact 3D mesh representation for storage or transmission. Various algorithms have been proposed since the early 1990s for efficiently compressing 3D meshes, e.g. “Technologies for 3D mesh compression: A survey”, by Jingliang Peng, Chang-Su Kim, C.-C. Jay Kuo, ELSEVIER Journal of Visual Communication and Image Representation, 2005, pp. 688-733. Moreover, a rapidly growing demand for 3D mesh models can be expected due to internet based 3D applications, e.g. games.
Typically, 3D meshes are represented by three types of data: connectivity data, geometry data and property data. Connectivity data describe the adjacency relationship between vertices, geometry data specify vertex locations, and property data specify attributes such as the normal vector, material reflectance and texture coordinates. Most 3D compression algorithms compress connectivity data and geometry data separately. The coding order of geometry data is determined by the underlying connectivity coding. Geometry data is usually compressed by three main steps: quantization, prediction and statistical encoding. 3D mesh property data are usually compressed in a similar manner.
The prediction step exploits the correlation between adjacent vertex positions, which is most crucial in improving geometry compression efficiency. The most widely used prediction strategy is parallelogram prediction, as proposed by literature [TG98] (C. Touma, C. Gotsman: “Triangle mesh compression”, Proceedings of Graphics Interface, 1998, pp. 26-34). This approach is shown in FIG. 1. The shaded area has already been encoded/decoded. The position of a new vertex r is predicted by the reference triangle Δuvw using the equationrp=u+v−w  (Eq.1)
Parallelogram prediction is based on the assumption that the four vertices u, v, w, r, are co-planar and construct a flat parallelogram. However, this basic assumption is not always true. In FIG. 1, there is a spatial angle θ between the reference triangle Δuvw and the new, so-called spanning triangle Δurv. This spatial angle, referred to as dihedral angle, is encoded. It defines the rotation of the spanning triangle Δurv around the common side uv that the reference triangle Δuvw, the co-planar prediction triangle Δurpv and the spanning triangle Δurv have. The prediction error or residual between the predicted vertex rp and the actual vertex r can be expressed as a vector resp.
Even for a simple model, such as a box shown in FIG. 2, the residual after parallelogram prediction may be quite big: the difference vector resp between the predicted vertex rp and the actual vertex r is even longer than a box side.
Typical failure cases are shown in FIG. 3 a). Triangles of the encoded/decoded area Aed are usually not co-planar. In one failure case, the new vertex c is not in the same plane with the reference triangle Δabd. Thus, the residual C1 is significant. Also in another failure case there is a significant difference C2 between a predicted position hp and an actual vertex h, although the new vertex h is in the same plane as the reference triangle Δfeg. To improve the prediction accuracy, [TG98] uses the dihedral angle θ shown in FIG. 3b) between Δebg and Δbdg to predict the neighboring dihedral angle between Δadb and Δabc. Another approach1 uses a multi-way parallelogram prediction scheme shown in FIG. 4. The multi-way prediction exploits all possible reference triangles and uses the average of all single-way predicted positions as the multi-way prediction result. [GA03]2 and [LAM02]3 divide vertex positions into tangential coordinates and dihedral angles, as shown in FIG. 5. The dihedral angle between the reference triangle and spanning triangle is predicted and encoded using this kind of local coordinate system. [GA03] fits a higher order surface to the encoded vertices and uses the high order surface to predict the dihedral angle α. 1 D. Cohen-Or, R. Cohen, and R. Irony: “Multiway geometry encoding”, Technical report, School of Computer Science, Tel Aviv University, 20022 S. Gumhold, R. Amjoun: “Higher order prediction of geometry compression”, Proceedings of the Shape Modeling International, Seoul, 2003, 59˜663 H. Lee, O. Allidz, M. Desbrun: “Angle-analyzer: A triangle-quad mesh codec”, Eurographics Conference Proceedings, 2002, 383˜392
Although many algorithms have been proposed to improve the accuracy of parallelogram prediction, vertices near sharp features, i.e. the area with highly varying curvature, still have relatively large residuals. The corresponding dihedral angles can not be deduced well from the reference triangles which are usually on the opposite side of the sharp feature. Most prediction schemes constrain the reference triangles to be on the same smooth surface as the spanning triangle, ie. the one that includes the actual new vertex. Although [GA03] works on making accurate prediction of the dihedral angle α, the vertices for fitting the high order surface are restricted in the already encoded and nearly flat region around the reference triangle, and the extra high order surface fitting step also significantly decreases the speed of both geometry encoder and decoder.
To improve geometry compression efficiency particularly of 3D meshes with lots of sharp features, such as typical 3D engineering models, an efficient prediction strategy specially designed for vertices on sharp features is needed.